By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

ALERT ATTENTION: System maintenance will be performed the weekend of Saturday, March 28, 2009. This event will begin at 6:00 am on March 28 and will conclude at approximately 12:00 noon on Sunday March 29 (all times EDT). Some Scitation services may be affected during this period.
Table of Contents
Search This Issue
Volume 23, Issue 3, pp. 449-669

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Top-Bottom Routing around a Rectangle is as Easy as Computing Prefix Minima

Omer Berkman, Joseph JáJá, Sridhar Krishnamurthy, Ramakrishna Thurimella, and Uzi Vishkin

pp. 449-465

BibTeX  Abstract Full Text:  PDF

Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts

Philip Klein, Serge Plotkin, Clifford Stein, and Éva Tardos

pp. 466-487

BibTeX  Abstract Full Text:  PDF

The Extended Low Hierarchy is an Infinite Hierarchy

Ming-Jye Sheu and Timothy J. Long

pp. 488-509

BibTeX  Abstract Full Text:  PDF

Complexity of Network Reliability and Optimal Resource Placement Problems

Donald B. Johnson and Larry Raab

pp. 510-519

BibTeX  Abstract Full Text:  PDF

Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs

Jitender S. Deogun and George Steiner

pp. 520-552

BibTeX  Abstract Full Text:  PDF

Packet Transmission in a Noisy-Channel Ring Network

Victor Pestien, S. Ramakrishnan, and Dilip Sarkar

pp. 553-562

BibTeX  Abstract Full Text:  PDF

Subquadratic Simulations of Balanced Formulae by Branching Programs

Jin-Yi Cai and Richard J. Lipton

pp. 563-572

BibTeX  Abstract Full Text:  PDF

Linear Time Algorithms and NP-Complete Problems

Etienne Grandjean

pp. 573-597

BibTeX  Abstract Full Text:  PDF

Digital Search Trees Again Revisited: The Internal Path Length Perspective

Peter Kirschenhofer, Helmut Prodinger, and Wojciech Szpankowski

pp. 598-616

BibTeX  Abstract Full Text:  PDF

Improved Approximation Algorithms for Shop Scheduling Problems

David B. Shmoys, Clifford Stein, and Joel Wein

pp. 617-632

BibTeX  Abstract Full Text:  PDF

Randomized Algorithms for Binary Search and Load Balancing on Fixed Connection Networks with Geometric Applications

John H. Reif and Sandeep Sen

pp. 633-651

BibTeX  Abstract Full Text:  PDF

Communication-Space Tradeoffs for Unrestricted Protocols

Paul Beame, Martin Tompa, and Peiyuan Yan

pp. 652-661

BibTeX  Abstract Full Text:  PDF

A New Insight into the Coffman–Graham Algorithm

Bertrand Braschi and Denis Trystram

pp. 662-669

BibTeX  Abstract Full Text:  PDF